package everydayone.maxqueue;

import java.util.LinkedList;

/**
 * @Date 2020/03/07
 * @author 王光浩
 * @Thingking 使用LinkedList来保存这个队列中的值，创建一个变量maxValue来保存最大值
 * @Analysis max_value、push_back的时间复杂度为O（1），pop_front的时间复杂度为O（n），空间复杂度O（n）
 */
public class MaxQueue {
	private int size;   //队列中数据的长度
	private int maxValue;   //保存最大值
	private LinkedList<Integer> queue;   //保存队列中的数据
	/**
	 * initial the maxQueue
	 */
    public MaxQueue() {
    	size=0;
    	maxValue=-1;
    	queue=new LinkedList<Integer>();
    }
    /**
     * @return the maxValue of the queue
     */
    public int max_value() {
    	return maxValue;
    }
    /**
     * push the element in the end of queue
     * @param
     */
    public void push_back(int value) {
    	if(value>maxValue)
    		maxValue=value;
    	queue.add(value);
    	size++;
    }
    /**
     * get the first element from the queue but the time is not O(1)
     * @return the first element from the queue
     */
    public int pop_front() {
    	if(size==0)
    		return -1;
    	size--;
    	int re=queue.poll();
    	if(re==maxValue)
    		find_max();
    	return re;
    }
    /**
     * find the max value from the queue
     */
    private void find_max() {
    	this.maxValue=-1;
    	for(int i:queue)
    		if(this.maxValue<i)
    			this.maxValue=i;
    }
}
